package mine.code.question.动态规划;

import com.sun.org.apache.bcel.internal.generic.ATHROW;
import org.junit.Test;

import java.util.Arrays;

/**
 * 给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
 * <p>
 * 假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
 * <p>
 * 返回多边形进行三角剖分后可以得到的最低分。
 * <p>
 * 输入：[3,7,4,5]
 * 输出：144
 * 解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
 *
 * @author caijinnan
 * @date 2020/5/26 17:02
 */
public class 多边形三角剖分的最低得分 {


    @Test
    public void run() {
        int[] A = {1, 3, 1, 4, 1, 5};
        System.out.println(minScoreTriangulation(A));
    }

    // dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + A[k - 1] * A[k] * A[k + 1]);
    public int minScoreTriangulation(int[] A) {
        int length = A.length;
        if (length <= 2) {
            return 0;
        }
        int[][] dp = new int[length][length];
        for (int[] temp : dp) {
            Arrays.fill(temp, Integer.MAX_VALUE);
        }
        for (int i = 0; i < length; i++) {
            dp[i][(i + 1)%length] = 0;
        }
        for (int len = 2; len < length; len++) {
            for (int i = 0; i + len < length; i++) {
                int j = i + len;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);
                }
            }
        }

        for (int[] temp : dp) {
            System.out.println(Arrays.toString(temp));
        }
        return dp[0][length - 1];
    }
}